{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Local Values in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestLocal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中的局部最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>n x n</code> 的整数矩阵 <code>grid</code> 。</p>\n",
    "\n",
    "<p>生成一个大小为&nbsp;<code>(n - 2) x (n - 2)</code> 的整数矩阵&nbsp; <code>maxLocal</code> ，并满足：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>maxLocal[i][j]</code> 等于 <code>grid</code> 中以 <code>i + 1</code> 行和 <code>j + 1</code> 列为中心的 <code>3 x 3</code> 矩阵中的 <strong>最大值</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>换句话说，我们希望找出 <code>grid</code> 中每个&nbsp;<code>3 x 3</code> 矩阵中的最大值。</p>\n",
    "\n",
    "<p>返回生成的矩阵。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/06/21/ex1.png\" style=\"width: 371px; height: 210px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]\n",
    "<strong>输出：</strong>[[9,9],[8,6]]\n",
    "<strong>解释：</strong>原矩阵和生成的矩阵如上图所示。\n",
    "注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/07/02/ex2new2.png\" style=\"width: 436px; height: 240px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]\n",
    "<strong>输出：</strong>[[2,2,2],[2,2,2],[2,2,2]]\n",
    "<strong>解释：</strong>注意，2 包含在 grid 中每个 3 x 3 的矩阵中。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-local-values-in-a-matrix](https://leetcode.cn/problems/largest-local-values-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-local-values-in-a-matrix](https://leetcode.cn/problems/largest-local-values-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]', '[[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        maxLocal: List[int] = []\n",
    "        for i in range(len(grid) - 2):\n",
    "            maxLocal.append([])\n",
    "            for j in range(len(grid[i]) - 2):\n",
    "                maxLocal[i].append(max(\n",
    "                    grid[p][q]\n",
    "                    for p in range(i, i + 3)\n",
    "                    for q in range(j, j + 3)\n",
    "                ))\n",
    "                \n",
    "        return maxLocal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        for i in range(n - 2):\n",
    "            for j in range(n - 2):\n",
    "                grid[i][j] = max(max(row[j:j + 3]) for row in grid[i:i + 3])\n",
    "            del grid[i][-2:]\n",
    "        del grid[-2:]  # 不要 return grid[:-2] 那样会有额外的拷贝\n",
    "        return grid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        res = [[0] * (n - 2) for _ in range(n - 2)]\n",
    "        for i in range(n - 2):\n",
    "            for j in range(n - 2):\n",
    "                res[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3))\n",
    "        return res \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        ans = [[0] * (n - 2) for _ in range(n - 2)]\n",
    "        for i in range(n - 2):\n",
    "            for j in range(n - 2):\n",
    "                ans[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        ans = [[0] * (n - 2) for _ in range(n - 2)]\n",
    "        for i in range(n - 2):\n",
    "            for j in range(n - 2):\n",
    "                ans[i][j] = max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        h=3\n",
    "        w=3\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        res=[[0]*m for _ in range(n)]\n",
    "        for i in range(m):\n",
    "            rxz=collections.deque()\n",
    "            for j in range(n):\n",
    "                while rxz and grid[i][j]>=grid[i][rxz[-1]]:rxz.pop()\n",
    "                while rxz and j-rxz[0]>=h:rxz.popleft()\n",
    "                rxz.append(j)\n",
    "                if j>=h-1:\n",
    "                    res[i][j]=grid[i][rxz[0]]\n",
    "        res2=[[0]*m for _ in range(n)]\n",
    "        for j in range(h-1,n):\n",
    "            rxz=collections.deque()\n",
    "            for i in range(m):\n",
    "                while rxz and res[i][j]>=res[rxz[-1]][j]:rxz.pop()\n",
    "                while rxz and i-rxz[0]>=w:rxz.popleft()\n",
    "                rxz.append(i)\n",
    "                if i>=w-1:\n",
    "                    res2[i][j]=res[rxz[0]][j]\n",
    "        for i in range(2,m):\n",
    "            res2[i]=res2[i][h-1:]\n",
    "        return res2[w-1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        m = len(grid)\n",
    "        res = [[[0] for i in range(m-2)] for j in range(m-2)]\n",
    "        for i in range(m-2):\n",
    "            for j in range(m-2):\n",
    "                ma = 0\n",
    "                for k in range(i, i+3):\n",
    "                    for h in range(j,j+3):\n",
    "                        ma = max(ma,grid[k][h])\n",
    "                res[i][j] = ma\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n = len(grid)\n",
    "        ans = [[0]*(n-2) for _ in range(n-2)]\n",
    "        for i in range(n-2):\n",
    "            for j in range(n-2):\n",
    "                ans[i][j] = max(grid[x][y] for x in range(i,i+3) for y in range(j,j+3))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        n=len(grid)\n",
    "        ans=[]\n",
    "        for i in range(0,n-2):\n",
    "            res=[]\n",
    "            for j in range(0,n-2):\n",
    "                maxrnum=0\n",
    "                for a in range(i,i+3):\n",
    "                    for b in range(j,j+3):\n",
    "                        maxrnum=max(maxrnum,grid[a][b])\n",
    "                res.append(maxrnum)\n",
    "            ans.append(res)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:\n",
    "        res = []\n",
    "        \n",
    "        n = len(grid)\n",
    "        \n",
    "        for i in range(n - 2):\n",
    "            layer = []\n",
    "            for j in range(n - 2):\n",
    "                temp = grid[i][j]\n",
    "                for u in range(i, i + 3):\n",
    "                    for v in range(j, j + 3):\n",
    "                        temp = max(temp, grid[u][v])\n",
    "                layer.append(temp)\n",
    "                # print(layer)\n",
    "            res.append(layer)\n",
    "        \n",
    "        return res\n",
    "                        \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
